//本题使用完全背包解法

#include<bits/stdc++.h>
using namespace std;

const int M = 2e5 + 9;
int bol[M];

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);			//读入优化
    int t;
    cin >> t;			//读入
    while (t--) {
        int n;
        cin >> n;			//读入
        vector <int> a(n + 3);
        int ma = 0;
        for (int i = 1 ; i <= n ; i ++) {
            cin >> a[i];
            ma = max(ma , a[i]);
        }
        
        sort(a.begin() + 1 , a.begin() + n + 1);					//把数组 a a a从小到大排序
        //遍历排序过的数组 a a a，用完全背包思想，把 a 中最大的数当作背包容量，扫一遍，能凑出来的打上标记，每打上一个新标记累加次数
        for (int i = 0 ; i < M ; i ++) 
        	bol[i] = 0;
        	int ans = 0;
        	for (int i = 1 ; i <= n ; i ++) {
            	if (bol[a[i]])
            		continue;
            	ans++;
            	bol[a[i]] = 1;
            for (int k = a[i];k <= ma;k++) {
                if (bol[k - a[i]])
                	bol[k] = 1;
            }
        }
        cout << ans << '\n';			//输出
    }
    return 0;
}
